class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int len = nums.size();
        int first = BinarySearch(nums, target, true);
        int last = BinarySearch(nums, target, false) - 1;
        if (first <= last && last < nums.size() && \
            nums[first] == target && nums[last] == target) {
            return vector<int> {first, last};
        } 
        return vector<int>{-1, -1};
    } 
private:
    int BinarySearch(vector<int>& nums, int target, bool flag){
        int len = nums.size();
        int left = 0, right = len - 1;
        int ret = len;
        while(left <= right){
            int mid = (left&right)+((left^right)>>1);
            if(nums[mid] > target || (flag && nums[mid] >= target)){
            // 如果为true找到第一个等于target的下标，false找到第一个大于target的下标   
                right = mid - 1;
                ret = mid;
            }else{
                left = mid + 1;
            }
        }
        return ret;
    }



/*
    vector<int> searchRange(vector<int>& nums, int target) {
        int len = nums.size();
        int first = FirstNum(nums, 0, len-1, target);
        int last = LastNum(nums, 0, len-1, target);
        vector<int> ret{first, last};
        return ret;
    }
private:
     //找到第一个 target 元素的下标
    int FirstNum(vector<int>& nums, int start, int end, int k){
        if(start > end){
            return -1;
        }

        //int mid = (start + end) / 2;
        int mid = (start&end)+((start^end)>>1);
        if(nums[mid] == k){
            if(mid > 0 && nums[mid - 1] != k
            || mid == 0){
                // nums[mid]正好是第一个k（前一个元素不等于k）
                return mid;  //返回第一个k的下标
            }
            else {
                end = mid - 1;
            }
        }
        else if(nums[mid] > k){
            end = mid - 1;
        }
        else{
            start = mid + 1;
        }
        return FirstNum(nums, start, end, k);
    }

    //找到最后一个 target 元素的下标
    int LastNum(vector<int>& nums, int start, int end, int k){
        if(start > end){
            return -1;
        }

        //int mid = (start + end) / 2;
        int mid = (start&end)+((start^end)>>1);
        if(nums[mid] == k){
            if(mid < nums.size() - 1 && nums[mid + 1] != k
            || mid == nums.size() - 1){
                // nums[mid]正好是最后一个k（后一个元素不等于k）
                return mid;
            }
            else {
                start = mid + 1;
            }
        }
        else if(nums[mid] > k){
            end = mid - 1;
        }
        else{
            start = mid + 1;
        }
        return LastNum(nums, start, end, k);
    }
*/
    
    
};